SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Quadratic pseudo-Boolean optimization</title>

</head>

Quadratic pseudo-Boolean optimization

</h1>

</header>

Quadratic pseudo-Boolean optimisation (QPBO) is a <a href="Combinatorial_optimization" title="Combinatorial optimization">combinatorial optimization</a> method for minimizing quadratic <a href="Pseudo-Boolean_function" title="Pseudo-Boolean function">pseudo-Boolean functions</a> in the form

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(\mathbf {x} )=w_{0}+\sum _{p\in V}w_{p}(x_{p})+\sum _{(p,q)\in E}w_{pq}(x_{p},x_{q})}</annotation>

</semantics>

</math><img src="./addace9e003b605a8095b155df6888e3f9c950d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:43.749ex; height:6.009ex;" alt="{\displaystyle f(\mathbf {x} )=w_{0}+\sum _{p\in V}w_{p}(x_{p})+\sum _{(p,q)\in E}w_{pq}(x_{p},x_{q})}" loading="lazy"></dd></dl>

in the <a href="Binary_data" title="Binary data">binary variables</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{p}\in \{0,1\}\;\forall p\in V=\{1,\dots ,n\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{p}\in \{0,1\}\;\forall p\in V=\{1,\dots ,n\}}</annotation>

</semantics>

</math><img src="./258e7b8b46c45fe88eb1007c6217072804b36cd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:31.807ex; height:3.009ex;" alt="{\displaystyle x_{p}\in \{0,1\}\;\forall p\in V=\{1,\dots ,n\}}" loading="lazy">, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E\subseteq V\times V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E\subseteq V\times V}</annotation>

</semantics>

</math><img src="./8068faae4df94a0ad4225ccce19f46530ae21de0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.289ex; height:2.343ex;" alt="{\displaystyle E\subseteq V\times V}" loading="lazy">. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is <a href="Pseudo-Boolean_function#Submodularity" title="Pseudo-Boolean function">submodular</a> then QPBO produces a global optimum equivalently to <a href="Graph_cut_optimization" title="Graph cut optimization">graph cut optimization</a>, while if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> contains non-submodular terms then the algorithm produces a partial solution with specific optimality properties, in both cases in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a>.<a href="#cite_note-review-1">[1]</a>

QPBO is a useful tool for inference on <a href="Markov_random_field" title="Markov random field">Markov random fields</a> and <a href="Conditional_random_field" title="Conditional random field">conditional random fields</a>, and has applications in <a href="Computer_vision" title="Computer vision">computer vision</a> problems such as <a href="Image_segmentation" title="Image segmentation">image segmentation</a> and <a href="Stereo_cameras" title="Stereo cameras">stereo matching</a>.<a href="#cite_note-rother-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Optimization_of_non-submodular_functions">Optimization of non-submodular functions</h2></div>

If the coefficients <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{pq}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{pq}}</annotation>

</semantics>

</math><img src="./563ba90a3fbb86a2bc3ce1021ba7f61dc18c6d75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.48ex; height:2.343ex;" alt="{\displaystyle w_{pq}}" loading="lazy"> of the quadratic terms satisfy the submodularity condition

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{pq}(0,0)+w_{pq}(1,1)\leq w_{pq}(0,1)+w_{pq}(1,0)}</annotation>

</semantics>

</math><img src="./e541a8ccd54f5be3a657ebedd72895f5ce5899b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:43.37ex; height:3.009ex;" alt="{\displaystyle w_{pq}(0,0)+w_{pq}(1,1)\leq w_{pq}(0,1)+w_{pq}(1,0)}" loading="lazy"></dd></dl>

then the function can be efficiently optimised with <a href="Graph_cut_optimization" title="Graph cut optimization">graph cut optimization</a>. It is indeed possible to represent it with a non-negative weighted <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a>, and the global minimum can be found in polynomial time by computing a <a href="Minimum_cut" title="Minimum cut">minimum cut</a> of the graph, which can be computed with algorithms such as <a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson</a>, <a href="Edmonds%E2%80%93Karp_algorithm" title="Edmonds–Karp algorithm">Edmonds–Karp</a>, and Boykov–Kolmogorov's.

If the function is not submodular, then the problem is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> in the general case and it is not always possible to solve it exactly in polynomial time. It is possible to replace the target function with a similar but submodular approximation, e.g. by removing all non-submodular terms or replacing them with submodular approximations, but such approach is generally sub-optimal and it produces satisfying results only if the number of non-submodular terms is relatively small.<a href="#cite_note-review-1">[1]</a>

QPBO builds an extended graph, introducing a set of auxiliary variables ideally equivalent to the negation of the variables in the problem. If the nodes in the graph associated to a variable (representing the variable itself and its negation) are separated by the <a href="Minimum_cut" title="Minimum cut">minimum cut</a> of the graph in two different connected components, then the optimal value for such variable is well defined, otherwise it is not possible to infer it. Such method produces results generally superior to submodular approximations of the target function.<a href="#cite_note-review-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>

QPBO produces a solution where each variable assumes one of three possible values: true, false, and undefined, noted in the following as 1, 0, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \emptyset }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \emptyset }</annotation>

</semantics>

</math><img src="./6af50205f42bb2ec3c666b7b847d2c7f96e464c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.162ex; height:2.509ex;" alt="{\displaystyle \emptyset }" loading="lazy"> respectively. The solution has the following two properties.

<ul><li>Partial optimality: if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is submodular, then QPBO produces a global minimum exactly, equivalent to <a href="Graph_cut_optimization" title="Graph cut optimization">graph cut</a>, and all variables have a non-undefined value; if submodularity is not satisfied, the result will be a partial solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

</math><img src="./32adf004df5eb0a8c7fd8c0b6b7405183c5a5ef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.411ex; height:1.676ex;" alt="{\displaystyle \mathbf {x} }" loading="lazy"> where a subset <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {V}}\subseteq V}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {V}}\subseteq V}</annotation>

</semantics>

</math><img src="./758ad028263c8a1858c7dc493c2291cb91c08664.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.673ex; height:3.009ex;" alt="{\displaystyle {\hat {V}}\subseteq V}" loading="lazy"> of the variables have a non-undefined value. A partial solution is always part of a global solution, i.e. there exists a global minimum point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x^{*}} }">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x^{*}} }</annotation>

</semantics>

</math><img src="./2ecbc9b12459ca3110630766af2cd0f072c42c91.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.588ex; height:2.343ex;" alt="{\displaystyle \mathbf {x^{*}} }" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}=x_{i}^{*}}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}=x_{i}^{*}}</annotation>

</semantics>

</math><img src="./295571ecf177efafc5d10ace5ba3c8dbd64371b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.612ex; height:2.843ex;" alt="{\displaystyle x_{i}=x_{i}^{*}}" loading="lazy"> for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in {\hat {V}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in {\hat {V}}}</annotation>

</semantics>

</math><img src="./d873c6e611c626a593f1f32e73392b71614080cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.43ex; height:2.843ex;" alt="{\displaystyle i\in {\hat {V}}}" loading="lazy">.</li>

<li>Persistence: given a solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

</math><img src="./32adf004df5eb0a8c7fd8c0b6b7405183c5a5ef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.411ex; height:1.676ex;" alt="{\displaystyle \mathbf {x} }" loading="lazy"> generated by QPBO and an arbitrary assignment of values <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} }</annotation>

</semantics>

</math><img src="./bb25a040b592282dc2a254c3117e792c3c81161f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.411ex; height:2.009ex;" alt="{\displaystyle \mathbf {y} }" loading="lazy"> to the variables, if a new solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {\mathbf {y} }}}">

<mover>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\mathbf {y} }}}</annotation>

</semantics>

</math><img src="./c3826fc591cfe42348f58b15e4c23152f30931ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.411ex; height:2.676ex;" alt="{\displaystyle {\hat {\mathbf {y} }}}" loading="lazy"> is constructed by replacing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}}</annotation>

</semantics>

</math><img src="./67d30d30b6c2dbe4d6f150d699de040937ecc95f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.939ex; height:2.009ex;" alt="{\displaystyle y_{i}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in {\hat {V}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in {\hat {V}}}</annotation>

</semantics>

</math><img src="./d873c6e611c626a593f1f32e73392b71614080cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.43ex; height:2.843ex;" alt="{\displaystyle i\in {\hat {V}}}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )}">

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )}</annotation>

</semantics>

</math><img src="./775bf6b3f4e48b58bf70761a00ebc721f11b3ee4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.096ex; height:2.843ex;" alt="{\displaystyle f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )}" loading="lazy">.<a href="#cite_note-review-1">[1]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

The algorithm can be divided in three steps: graph construction, max-flow computation, and assignment of values to the variables.

When constructing the graph, the set of vertices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> contains the source and sink nodes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">, and a pair of nodes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p'}</annotation>

</semantics>

</math><img src="./40e623e3163571a220ed60ecb31aa78c24104b85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.944ex; height:2.843ex;" alt="{\displaystyle p'}" loading="lazy"> for each variable. After re-parametrising the function to normal form,<a href="#cite_note-normal_form-3">[note 1]</a> a pair of edges is added to the graph for each term <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy">:

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{p}(0)}</annotation>

</semantics>

</math><img src="./51c2bc032d17cc3bcbaf5094ebe0cb41ee3c95ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.695ex; height:3.009ex;" alt="{\displaystyle w_{p}(0)}" loading="lazy"> the edges <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\rightarrow t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\rightarrow t}</annotation>

</semantics>

</math><img src="./b1b3fc3c5bf09871ead4ba2542be6ebc35858046.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.713ex; height:2.343ex;" alt="{\displaystyle p\rightarrow t}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\rightarrow p'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\rightarrow p'}</annotation>

</semantics>

</math><img src="./fb865acf9ee87f57ceb136f115cebe1401edc005.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.559ex; height:2.843ex;" alt="{\displaystyle s\rightarrow p'}" loading="lazy">, with weight <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{2}}w_{p}(0)}">

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{2}}w_{p}(0)}</annotation>

</semantics>

</math><img src="./3f17095b2f7ab6ea34fb6428bb7c3146476da9fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:7.694ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{2}}w_{p}(0)}" loading="lazy">;</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{p}(1)}</annotation>

</semantics>

</math><img src="./d900ad60c0afa12474c69d9e47e4e23f9190e2d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.695ex; height:3.009ex;" alt="{\displaystyle w_{p}(1)}" loading="lazy"> the edges <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\rightarrow p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\rightarrow p}</annotation>

</semantics>

</math><img src="./f2398557a8a4f862253386b4c5339e8fdf2616b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.874ex; height:2.176ex;" alt="{\displaystyle s\rightarrow p}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p'\rightarrow t}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p'\rightarrow t}</annotation>

</semantics>

</math><img src="./e71eb29e1439ef9ccac953cc171ae003a59baf43.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:6.397ex; height:2.843ex;" alt="{\displaystyle p'\rightarrow t}" loading="lazy">, with weight <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{2}}w_{p}(1)}">

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{2}}w_{p}(1)}</annotation>

</semantics>

</math><img src="./eeada8ee146565ec3084d40fc85126c958fcab68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:7.694ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{2}}w_{p}(1)}" loading="lazy">;</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{pq}(0,1)}</annotation>

</semantics>

</math><img src="./c5e30097cf11ba77c8e48676477b6161b9089642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.648ex; height:3.009ex;" alt="{\displaystyle w_{pq}(0,1)}" loading="lazy"> the edges <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\rightarrow q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\rightarrow q}</annotation>

</semantics>

</math><img src="./4e3f9e5de9aaead8d19411bb3ad0dc490a50ec69.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.942ex; height:2.176ex;" alt="{\displaystyle p\rightarrow q}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q'\rightarrow p'}">

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q'\rightarrow p'}</annotation>

</semantics>

</math><img src="./7ddbc636275bdfa55f23af2eb8a6627669ab1c5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.232ex; height:2.843ex;" alt="{\displaystyle q'\rightarrow p'}" loading="lazy">, with weight <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{2}}w_{pq}(0,1)}">

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{2}}w_{pq}(0,1)}</annotation>

</semantics>

</math><img src="./b7b21e55897c5e47cc0634831dd86228e918a54f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:10.646ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{2}}w_{pq}(0,1)}" loading="lazy">;</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{pq}(1,0)}</annotation>

</semantics>

</math><img src="./8ad4699d58db02940dd97b4965b1b1ac33d5e91b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.648ex; height:3.009ex;" alt="{\displaystyle w_{pq}(1,0)}" loading="lazy"> the edges <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q\rightarrow p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q\rightarrow p}</annotation>

</semantics>

</math><img src="./f0c4b7a404e70f10b9e0734cf1d64777619bf271.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.853ex; height:2.176ex;" alt="{\displaystyle q\rightarrow p}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p'\rightarrow q'}">

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p'\rightarrow q'}</annotation>

</semantics>

</math><img src="./a2b478676732adb942862607e889b0d3ad75348a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:7.322ex; height:2.843ex;" alt="{\displaystyle p'\rightarrow q'}" loading="lazy">, with weight <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{2}}w_{pq}(1,0)}">

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{2}}w_{pq}(1,0)}</annotation>

</semantics>

</math><img src="./1ffcabd9b223a7be673d682fef3b0ee63a60184e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:10.646ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{2}}w_{pq}(1,0)}" loading="lazy">;</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{pq}(0,0)}</annotation>

</semantics>

</math><img src="./a75b95367f90cdedbc657b19c549c3683d892572.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.648ex; height:3.009ex;" alt="{\displaystyle w_{pq}(0,0)}" loading="lazy"> the edges <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\rightarrow q'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\rightarrow q'}</annotation>

</semantics>

</math><img src="./2ae20589b501566480794b3fbdf3f1b092142af7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:6.637ex; height:2.843ex;" alt="{\displaystyle p\rightarrow q'}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q\rightarrow p'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q\rightarrow p'}</annotation>

</semantics>

</math><img src="./da4bc2d696822559dea36fe27d73425b34c09c63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.538ex; height:2.843ex;" alt="{\displaystyle q\rightarrow p'}" loading="lazy">, with weight <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{2}}w_{pq}(0,0)}">

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{2}}w_{pq}(0,0)}</annotation>

</semantics>

</math><img src="./5b9e42d3502eb3667221416483b4d0b7da45b95a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:10.646ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{2}}w_{pq}(0,0)}" loading="lazy">;</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{pq}(1,1)}</annotation>

</semantics>

</math><img src="./c9a1fe1dd2254a5d3870fa05f6ec0db5458e7467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.648ex; height:3.009ex;" alt="{\displaystyle w_{pq}(1,1)}" loading="lazy"> the edges <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q'\rightarrow p}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q'\rightarrow p}</annotation>

</semantics>

</math><img src="./3d9a64b69e7cbf238edc445a4a91c32f587cb48d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.548ex; height:2.843ex;" alt="{\displaystyle q'\rightarrow p}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p'\rightarrow q}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p'\rightarrow q}</annotation>

</semantics>

</math><img src="./983cd2d4e981cdf6646935e3dc3c798b09b882dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:6.627ex; height:2.843ex;" alt="{\displaystyle p'\rightarrow q}" loading="lazy">, with weight <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{2}}w_{pq}(1,1)}">

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{2}}w_{pq}(1,1)}</annotation>

</semantics>

</math><img src="./238be2bd3e18084775c2139f978e1dab2a58b15a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:10.646ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{2}}w_{pq}(1,1)}" loading="lazy">.</li></ul>

The <a href="Minimum_cut" title="Minimum cut">minimum cut</a> of the graph can be computed with a <a href="Max-flow_min-cut_theorem" title="Max-flow min-cut theorem">max-flow algorithm</a>. In the general case, the minimum cut is not unique, and each minimum cut correspond to a different partial solution, however it is possible to build a minimum cut such that the number of undefined variables is minimal.

Once the minimum cut is known, each variable receives a value depending upon the position of its corresponding nodes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p'}</annotation>

</semantics>

</math><img src="./40e623e3163571a220ed60ecb31aa78c24104b85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.944ex; height:2.843ex;" alt="{\displaystyle p'}" loading="lazy">: if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> belongs to the connected component containing the source and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p'}</annotation>

</semantics>

</math><img src="./40e623e3163571a220ed60ecb31aa78c24104b85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.944ex; height:2.843ex;" alt="{\displaystyle p'}" loading="lazy"> belongs to the connected component containing the sink then the variable will have value of 0. Vice versa, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> belongs to the connected component containing the sink and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p'}</annotation>

</semantics>

</math><img src="./40e623e3163571a220ed60ecb31aa78c24104b85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.944ex; height:2.843ex;" alt="{\displaystyle p'}" loading="lazy"> to the one containing the source, then the variable will have value of 1. If both nodes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p'}</annotation>

</semantics>

</math><img src="./40e623e3163571a220ed60ecb31aa78c24104b85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.944ex; height:2.843ex;" alt="{\displaystyle p'}" loading="lazy"> belong to the same connected component, then the value of the variable will be undefined.<a href="#cite_note-rother-2">[2]</a>

The way undefined variables can be handled is dependent upon the context of the problem. In the general case, given a <a href="Partition_of_a_set" title="Partition of a set">partition</a> of the graph in two sub-graphs and two solutions, each one optimal for one of the sub-graphs, then it is possible to combine the two solutions into one solution optimal for the whole graph in polynomial time.<a href="#cite_note-billionnet-4">[3]</a> However, computing an optimal solution for the subset of undefined variables is still a <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> problem. In the context of iterative algorithms such as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy">-expansion, a reasonable approach is to leave the value of undefined variables unchanged, since the persistence property guarantees that the target function will have non-increasing value.<a href="#cite_note-review-1">[1]</a> Different exact and approximate strategies to minimise the number of undefined variables exist.<a href="#cite_note-rother-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Higher_order_terms">Higher order terms</h2></div>

It is always possible to reduce a higher-order function to a quadratic function which is equivalent with respect to the optimisation, problem known as "higher-order <a href="Clique_(graph_theory)" title="Clique (graph theory)">clique</a> reduction" (HOCR), and the result of such reduction can be optimized with QPBO. Generic methods for reduction of arbitrary functions rely on specific substitution rules and in the general case they require the introduction of auxiliary variables.<a href="#cite_note-fix-5">[4]</a> In practice most terms can be reduced without introducing additional variables, resulting in a simpler optimization problem, and the remaining terms can be reduced exactly, with addition of auxiliary variables, or approximately, without addition of any new variable.<a href="#cite_note-elc-6">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

<li id="cite_note-review-1">^ <a href="#cite_ref-review_1-0">a</a> <a href="#cite_ref-review_1-1">b</a> <a href="#cite_ref-review_1-2">c</a> <a href="#cite_ref-review_1-3">d</a> <a href="#cite_ref-review_1-4">e</a> Kolmogorov and Rother (2007).

</li>

<li id="cite_note-rother-2">^ <a href="#cite_ref-rother_2-0">a</a> <a href="#cite_ref-rother_2-1">b</a> <a href="#cite_ref-rother_2-2">c</a> Rother et al. (2007).

</li>

<li id="cite_note-billionnet-4"><a href="#cite_ref-billionnet_4-0">^</a> Billionnet and Jaumard (1989).

</li>

<li id="cite_note-fix-5"><a href="#cite_ref-fix_5-0">^</a> Fix et al. (2011).

</li>

<li id="cite_note-elc-6"><a href="#cite_ref-elc_6-0">^</a> Ishikawa (2014).

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBillionnetJaumard1989" class="citation journal cs1">Billionnet, Alain; <a href="Brigitte_Jaumard" title="Brigitte Jaumard">Jaumard, Brigitte</a> (1989). "A decomposition method for minimizing quadratic pseudo-boolean functions". <a href="Operations_Research_Letters" title="Operations Research Letters">Operations Research Letters</a>. 8 (3): 161–163. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0167-6377%2889%2990043-6">10.1016/0167-6377(89)90043-6</a>.</cite></li>

<li><cite id="CITEREFFixGruberBorosZabih2011" class="citation conference cs1">Fix, Alexander; Gruber, Aritanan; Boros, Endre; Zabih, Ramin (2011). <a rel="nofollow" class="external text" href="https://www.cs.cornell.edu/~afix/Papers/ICCV11.pdf">A graph cut algorithm for higher-order Markov random fields</a> (PDF). <a href="International_Conference_on_Computer_Vision" title="International Conference on Computer Vision">International Conference on Computer Vision</a>. pp. 1020–1027.</cite></li>

<li><cite id="CITEREFIshikawa2014" class="citation conference cs1">Ishikawa, Hiroshi (2014). <a rel="nofollow" class="external text" href="https://www.cv-foundation.org/openaccess/content_cvpr_2014/papers/Ishikawa_Higher-Order_Clique_Reduction_2014_CVPR_paper.pdf">Higher-Order Clique Reduction Without Auxiliary Variables</a> (PDF). <a href="Conference_on_Computer_Vision_and_Pattern_Recognition" title="Conference on Computer Vision and Pattern Recognition">Conference on Computer Vision and Pattern Recognition</a>. IEEE. pp. 1362–1269.</cite></li>

<li><cite id="CITEREFKolmogorovRother2007" class="citation journal cs1">Kolmogorov, Vladimir; Rother, Carsten (2007). "Minimizing Nonsubmodular Functions: A Review". <a href="IEEE_Transactions_on_Pattern_Analysis_and_Machine_Intelligence" title="IEEE Transactions on Pattern Analysis and Machine Intelligence">IEEE Transactions on Pattern Analysis and Machine Intelligence</a>. 29 (7). IEEE: 1274–1279. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftpami.2007.1031">10.1109/tpami.2007.1031</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/17496384">17496384</a>.</cite></li>

<li><cite id="CITEREFRotherKolmogorovLempitskySzummer2007" class="citation conference cs1">Rother, Carsten; Kolmogorov, Vladimir; Lempitsky, Victor; Szummer, Martin (2007). <a rel="nofollow" class="external text" href="https://www.microsoft.com/en-us/research/wp-content/uploads/2007/06/cvpr07-QPBOpi-TR.pdf">Optimizing binary MRFs via extended roof duality</a> (PDF). <a href="Conference_on_Computer_Vision_and_Pattern_Recognition" title="Conference on Computer Vision and Pattern Recognition">Conference on Computer Vision and Pattern Recognition</a>. pp. 1–8.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes_2">Notes</h2></div>

<li id="cite_note-normal_form-3"><a href="#cite_ref-normal_form_3-0">^</a> The representation of a pseudo-Boolean function with coefficients <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {w} =(w_{0},w_{1},\dots ,w_{nn})}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {w} =(w_{0},w_{1},\dots ,w_{nn})}</annotation>

</semantics>

</math><img src="./dfa1decf35af419ce8ed4012cd66041d36ca9290.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.357ex; height:2.843ex;" alt="{\displaystyle \mathbf {w} =(w_{0},w_{1},\dots ,w_{nn})}" loading="lazy"> is not unique, and if two coefficient vectors <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {w} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {w} }</annotation>

</semantics>

</math><img src="./20795664b5b048744a2fd88977851104cc5816f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.931ex; height:1.676ex;" alt="{\displaystyle \mathbf {w} }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {w} '}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {w} '}</annotation>

</semantics>

</math><img src="./32350e04aaac36413dcc1ee9b766d28d8d2ce3c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.616ex; height:2.509ex;" alt="{\displaystyle \mathbf {w} '}" loading="lazy"> represent the same function then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {w} '}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {w} '}</annotation>

</semantics>

</math><img src="./32350e04aaac36413dcc1ee9b766d28d8d2ce3c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.616ex; height:2.509ex;" alt="{\displaystyle \mathbf {w} '}" loading="lazy"> is said to be a reparametrisation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {w} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {w} }</annotation>

</semantics>

</math><img src="./20795664b5b048744a2fd88977851104cc5816f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.931ex; height:1.676ex;" alt="{\displaystyle \mathbf {w} }" loading="lazy"> and vice versa. In some constructions it is useful to ensure that the function has a specific form, called normal form, which is always defined for any function, and it is not unique. A function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is in normal form if the two following conditions hold (Kolmogorov and Rother (2007)):

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min\{w_{p}^{0},w_{p}^{1}\}=0}</annotation>

</semantics>

</math><img src="./597c530ee9c0b9d8e1d31beb55b7a22e3b805f7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.942ex; height:3.176ex;" alt="{\displaystyle \min\{w_{p}^{0},w_{p}^{1}\}=0}" loading="lazy"> for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\in V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\in V}</annotation>

</semantics>

</math><img src="./bda12e4b7ca69e1ebd441e92740b10245434ac5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.887ex; height:2.509ex;" alt="{\displaystyle p\in V}" loading="lazy">;</li>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min\{w_{pq}^{0j},w_{pq}^{1j}\}=0}</annotation>

</semantics>

</math><img src="./866701baa9d5c3251d2041d401104d42e5ee0237.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:18.454ex; height:3.509ex;" alt="{\displaystyle \min\{w_{pq}^{0j},w_{pq}^{1j}\}=0}" loading="lazy"> for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (p,q)\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (p,q)\in E}</annotation>

</semantics>

</math><img src="./617820b110925034dd68ff6c96c13dbf20440567.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.698ex; height:2.843ex;" alt="{\displaystyle (p,q)\in E}" loading="lazy"> and for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j\in \{0,1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j\in \{0,1\}}</annotation>

</semantics>

</math><img src="./74b3fddc2d9db783efffa1dd96c1ccc76ff70381.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.027ex; width:9.509ex; height:2.843ex;" alt="{\displaystyle j\in \{0,1\}}" loading="lazy">.</li></ol>

Given an arbitrary function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">, it is always possible to find a reparametrisation to normal form with the following algorithm in two steps (Kolmogorov and Rother (2007)):

<ol><li>as long as there exist indices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (p,q)\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (p,q)\in E}</annotation>

</semantics>

</math><img src="./617820b110925034dd68ff6c96c13dbf20440567.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.698ex; height:2.843ex;" alt="{\displaystyle (p,q)\in E}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j\in \{0,1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j\in \{0,1\}}</annotation>

</semantics>

</math><img src="./74b3fddc2d9db783efffa1dd96c1ccc76ff70381.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.027ex; width:9.509ex; height:2.843ex;" alt="{\displaystyle j\in \{0,1\}}" loading="lazy"> such that the second condition of normality is not satisfied, substitute:

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{pq}^{0j}}</annotation>

</semantics>

</math><img src="./b9d63903cf689d6cde2799738e735df4571e89d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.48ex; height:3.509ex;" alt="{\displaystyle w_{pq}^{0j}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{pq}^{0j}-a}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{pq}^{0j}-a}</annotation>

</semantics>

</math><img src="./4e16ed6dc3434a27e6a117fa6078747ee3069a44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.55ex; height:3.509ex;" alt="{\displaystyle w_{pq}^{0j}-a}" loading="lazy"></li>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{pq}^{1j}}</annotation>

</semantics>

</math><img src="./de4b146d97eef5d9c837c90dd89349467b258e4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.48ex; height:3.509ex;" alt="{\displaystyle w_{pq}^{1j}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{pq}^{1j}-a}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{pq}^{1j}-a}</annotation>

</semantics>

</math><img src="./06803143d5dffc1e34231ae1c348ea2aab21c9c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.55ex; height:3.509ex;" alt="{\displaystyle w_{pq}^{1j}-a}" loading="lazy"></li>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{q}^{j}}</annotation>

</semantics>

</math><img src="./a4f47648c046a26b96aaa028ce52730855531f1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.653ex; height:3.343ex;" alt="{\displaystyle w_{q}^{j}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{q}^{j}+a}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{q}^{j}+a}</annotation>

</semantics>

</math><img src="./b5d647b690d9458ad331c71a3fe2dcfb9d44582d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.723ex; height:3.343ex;" alt="{\displaystyle w_{q}^{j}+a}" loading="lazy"></li></ul>

<dl><dd>where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}}</annotation>

</semantics>

</math><img src="./f7e64e137aa42cad6847af4efe99cca9e2c18e97.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:18.522ex; height:3.509ex;" alt="{\displaystyle a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}}" loading="lazy">;</dd></dl></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p=1,\dots ,n}</annotation>

</semantics>

</math><img src="./57c1fffa983253e11a686f6b785e8771b1fc57c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:12.093ex; height:2.509ex;" alt="{\displaystyle p=1,\dots ,n}" loading="lazy">, substitute:

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{0}}</annotation>

</semantics>

</math><img src="./7aa052386ec49846179aa8bbe2b279b57a675e00.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.718ex; height:2.009ex;" alt="{\displaystyle w_{0}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{0}+a}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{0}+a}</annotation>

</semantics>

</math><img src="./ba6e7e3bc7f30fd03a6b55b1d6c0aafba97bcff3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.789ex; height:2.343ex;" alt="{\displaystyle w_{0}+a}" loading="lazy"></li>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{p}^{0}}</annotation>

</semantics>

</math><img src="./51216f1459dce9d9d9d47b9a60c8bae13987f4d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.723ex; height:3.176ex;" alt="{\displaystyle w_{p}^{0}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{p}^{0}-a}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{p}^{0}-a}</annotation>

</semantics>

</math><img src="./14ee65ca6dc7126fe2c18c6d7f90ccc2325d5c90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.794ex; height:3.176ex;" alt="{\displaystyle w_{p}^{0}-a}" loading="lazy"></li>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{p}^{1}}</annotation>

</semantics>

</math><img src="./5884b7df74999d3d0400c9d8a05120566d3d941b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.723ex; height:3.176ex;" alt="{\displaystyle w_{p}^{1}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{p}^{1}-a}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{p}^{1}-a}</annotation>

</semantics>

</math><img src="./9f992463da335dac37f74459bb2aaf026196baed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.794ex; height:3.176ex;" alt="{\displaystyle w_{p}^{1}-a}" loading="lazy"></li></ul>

<dl><dd>where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=\min\{w_{p}^{0},w_{p}^{1}\}}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=\min\{w_{p}^{0},w_{p}^{1}\}}</annotation>

</semantics>

</math><img src="./12eda02f8e057bbb1900cb1dcfef49711c7f9390.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.009ex; height:3.176ex;" alt="{\displaystyle a=\min\{w_{p}^{0},w_{p}^{1}\}}" loading="lazy">.</dd></dl></li></ol>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://pub.ist.ac.at/~vnk/software.html#qpbo">Implementation of QPBO (C++)</a>, available under the <a href="GNU_General_Public_License" title="GNU General Public License">GNU General Public License</a>, by Vladimir Kolmogorov.</li>

<li><a rel="nofollow" class="external text" href="http://www.f.waseda.jp/hfs/software.html">Implementation of HOCR (C++)</a>, available under the <a href="MIT_license" class="mw-redirect" title="MIT license">MIT license</a>, by Hiroshi Ishikawa.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-06-13" href="https://en.wikipedia.org/wiki/?title=Quadratic_pseudo-Boolean_optimization&oldid=1228816220">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>